\documentclass[12pt,openany,a4paper]{book}
\usepackage{graphics}	% if you want encapsulated PS figures.
\usepackage{mathtools}
\usepackage{algorithm2e}
\usepackage{listings}

% If you use a macro file called macros.tex :
% \input{macros}
% Note: The present document has its macros built in.

% Number subsections but not subsubsections:
\setcounter{secnumdepth}{2}
% Show subsections but not subsubsections in table of contents:
\setcounter{tocdepth}{2}

\pagestyle{headings}		% Chapter on left page, Section on right.
\raggedbottom

\setlength{\topmargin}		{-5mm}  %  25-5 = 20mm
\setlength{\oddsidemargin}	{10mm}  % rhs page inner margin = 25+10mm
\setlength{\evensidemargin}	{0mm}   % lhs page outer margin = 25mm
\setlength{\textwidth}		{150mm} % 35 + 150 + 25 = 210mm
\setlength{\textheight}		{240mm} % 

\renewcommand{\baselinestretch}{1.2}	% Looks like 1.5 spacing.

% Stop figure/tables smaller than 3/4 page from appearing alone on a page:
\renewcommand{\textfraction}{0.25}
\renewcommand{\topfraction}{0.75}
\renewcommand{\bottomfraction}{0.75}
\renewcommand{\floatpagefraction}{0.75}

% THEOREM-LIKE ENVIRONMENTS:
\newtheorem{defn}	{Definition}	% cf. \dfn for cross-referencing
\newtheorem{theorem}	{Theorem}	% cf. \thrm for cross-referencing
\newtheorem{lemma}	{Lemma}		% cf. \lem for cross-referencing

% AIDS TO CROSS-REFERENCING (All take a label as argument):
\newcommand{\eref}[1] {(\ref{#1})}		% (...)
\newcommand{\eq}[1]   {Eq.\,(\ref{#1})}		% Eq.~(...)
\newcommand{\eqs}[2]  {Eqs.~(\ref{#1}) and~(\ref{#2})}
\newcommand{\dfn}[1]  {Definition~\ref{#1}}	% Definition~...
\newcommand{\thrm}[1] {Theorem~\ref{#1}}	% Theorem~...
\newcommand{\lem}[1]  {Lemma~\ref{#1}}		% Lemma~...
\newcommand{\fig}[1]  {Fig.\,\ref{#1}}		% Fig.~...
\newcommand{\tab}[1]  {Table~\ref{#1}}		% Table~...
\newcommand{\chap}[1] {Chapter~\ref{#1}}	% Chapter~...
\newcommand{\secn}[1] {Section~\ref{#1}}	% Section~...
\newcommand{\ssec}[1] {Subsection~\ref{#1}}	% Subsection~...

% AIDS TO FORMATTING:
\newcommand{\teq}[1]	{\mbox{$#1$}}	% in-Text EQuation (unbreakable)
\newcommand{\qed}	{\hspace*{\fill}$\bullet$}	% end of proof

% MATHEMATICAL TEMPLATES:
% Text or math mode:
\newcommand{\half}	{\ensuremath{\frac{1}{2}}}	% one-half
\newcommand{\halftxt}	{\mbox{$\frac{1}{2}$}}	  	% one-half, small
% Math mode only:
% N.B. Parentheses are ROUND; brackets are SQUARE!
\newcommand{\oneon}[1]	{\frac{1}{#1}}		  % reciprocal
\newcommand{\pow}[2]	{\left({#1}\right)^{#2}}  % Parenthesized pOWer
\newcommand{\bow}[2]	{\left[{#1}\right]^{#2}}  % Bracketed pOWer
\newcommand{\evalat}[2]	{\left.{#1}\right|_{#2}}  % EVALuated AT with bar
\newcommand{\bevalat}[2]{\left[{#1}\right]_{#2}}  % Bracketed EVALuated AT
% Total derivatives:
\newcommand{\sdd}[2]	{\frac{d{#1}}{d{#2}}}		    % Short
\newcommand{\sqdd}[2]	{\frac{d^2{#1}}{d{#2}^2}}	    % 2nd ("SQuared")
\newcommand{\ldd}[2]	{\frac{d}{d{#1}}\left({#2}\right)}  % Long paren'ed
\newcommand{\bdd}[2]	{\frac{d}{d{#2}}\left[{#2}\right]}  % long Bracketed
% Partial derivatives (same sequence as for total derivatives):
\newcommand{\sdada}[2]	{\frac{\partial {#1}}{\partial {#2}}}
\newcommand{\sqdada}[2]	{\frac{\partial ^{2}{#1}}{\partial {#2}^{2}}}
\newcommand{\ldada}[2]	{\frac{\partial}{\partial {#1}}\left({#2}\right)}
\newcommand{\bdada}[2]	{\frac{\partial}{\partial {#1}}\left[{#2}\right]}
\newcommand{\da}	{\partial}

% ORDINAL NUMBERS:
\newcommand{\ith}	{\ensuremath{i^{\rm th}}}
\newcommand{\jth}	{\ensuremath{j^{\rm th}}}
\newcommand{\kth}	{\ensuremath{k^{\rm th}}}
\newcommand{\lth}	{\ensuremath{l^{\rm th}}}
\newcommand{\mth}	{\ensuremath{m^{\rm th}}}
\newcommand{\nth}	{\ensuremath{n^{\rm th}}}

% SINUSOIDAL TIME AND SPACE-DEPENDENCY FACTORS:
\newcommand{\ejot}	{\ensuremath{e^{j\omega t}}}
\newcommand{\emjot}	{\ensuremath{e^{-j\omega t}}}

% UNITS (TEXT OR MATH MODE, WITH LEADING PADDING SPACE IF APPLICABLE):
% NB: These have not been tested since being modified for LaTeX2e.
\newcommand{\pack}	{\hspace{-0.08em}}
\newcommand{\Pack}	{\hspace{-0.12em}}
\newcommand{\mA}	{\ensuremath{\rm\,m\pack A}}
\newcommand{\dB}	{\ensuremath{\rm\,d\pack B}}
\newcommand{\dBm}	{\ensuremath{\rm\,d\pack B\pack m}}
\newcommand{\dBW}	{\ensuremath{\rm\,d\pack B\Pack W}}
\newcommand{\uF}	{\ensuremath{\rm\,\mu\pack F}}
\newcommand{\pF}	{\ensuremath{\rm\,p\pack F}}
\newcommand{\nF}	{\ensuremath{\rm\,n\pack F}}
\newcommand{\uH}	{\ensuremath{\rm\,\mu\pack H}}
\newcommand{\mH}	{\ensuremath{\rm\,m\pack H}}
\newcommand{\Hz}	{\ensuremath{\rm\,H\pack z}}
\newcommand{\kHz}	{\ensuremath{\rm\,k\pack H\pack z}}
\newcommand{\MHz}	{\ensuremath{\rm\,M\pack H\pack z}}
\newcommand{\GHz}	{\ensuremath{\rm\,G\pack H\pack z}}
\newcommand{\J}		{\ensuremath{\rm\,J}}
\newcommand{\kg}	{\ensuremath{\rm\,k\pack g}}
\newcommand{\K}		{\ensuremath{\rm\,K}}
\newcommand{\m}		{\ensuremath{\rm\,m}}
\newcommand{\cm}	{\ensuremath{\rm\,cm}}
\newcommand{\km}	{\ensuremath{\rm\,k\pack m}}
\newcommand{\mm}	{\ensuremath{\rm\,m\pack m}}
\newcommand{\nm}	{\ensuremath{\rm\,n\pack m}}
\newcommand{\um}	{\ensuremath{\rm\,\mu m}}
\newcommand{\Np}	{\ensuremath{\rm\,N\pack p}}
\newcommand{\s}		{\ensuremath{\rm\,s}}
\newcommand{\ms}	{\ensuremath{\rm\,m\pack s}}
\newcommand{\us}	{\ensuremath{\rm\,\mu s}}
\newcommand{\V}		{\ensuremath{\rm\,V}}
\newcommand{\mV}	{\ensuremath{\rm\,m\Pack V}}
\newcommand{\W}		{\ensuremath{\rm\,W}}
\newcommand{\mW}	{\ensuremath{\rm\,m\Pack W}}
\newcommand{\ohm}	{\ensuremath{\rm\,\Omega}}
\newcommand{\kohm}	{\ensuremath{\rm\,k\Omega}}
\newcommand{\Mohm}	{\ensuremath{\rm\,M\Omega}}
\newcommand{\degs}	{\ensuremath{\rm^{\circ}}}

% LaTeX run-time type-in command:
%
% \typein{Enter \protect\includeonly{...} command (or just type RETURN):}
%
% Uncommenting this command makes LaTeX prompt you for the \includeonly
% list.  At the prompt
%
%	\@typein=
%
% you type
%
%	\includeonly{chap1,chap2}
%
% to include the files chap1.tex and chap2.tex and omit any others.
% To include every \include file, just hit RETURN.
% If you are running LaTeX from xtexsh, you may need to click the mouse
% in the LaTeX window to position the cursor at the \@typein prompt.

\begin{document}


\frontmatter
% By default, frontmatter has Roman page-numbering (i,ii,...).

\begin{titlepage}
\renewcommand{\baselinestretch}{1.0}
\begin{center}
\vspace*{35mm}
\Huge\bf
		Tree\\
		Distance Metric\\
		Comparison\\
\vspace{20mm}
\large\sl
		by\\
		Charles Murray 42057901
		\medskip\\
\rm
		Department of Electrical and Computer Engineering,\\
		University of Queensland.\\
\vspace{30mm}
		Submitted for the degree of\\
		Bachelor of Engineering
		\smallskip\\
\normalsize
		in the division of Software
		\medskip\\
\large
		06 \& 2013.		
\end{center}
\end{titlepage}

\cleardoublepage

\begin{flushright}
	5 Malparara Place\\
	Carseldine\\
	Tel.\ (07) 3263 5456\\
	\medskip
	\today
\end{flushright}
\begin{flushleft}
  The Dean\\
  School of Engineering\\
  University of Queensland\\
  St Lucia, Q 4072\\
  \bigskip\bigskip
  Dear Professor Simmons,
\end{flushleft}

In accordance with the requirements of the degree of Bachelor of
Engineering in the division of Software Engineering, I present the
following thesis entitled 'Tree Distance Metric Comparison'.  This work was performed 
 under the supervision of
Dr Xue Li.

I declare that the work submitted in this thesis is my own, except as
acknowledged in the text and footnotes, and has not been previously
submitted for a degree at the University of Queensland or any other
institution.

\begin{flushright}
	Yours sincerely,\\
	\medskip
	\medskip
	Charles Murray.
\end{flushright}

\cleardoublepage

% Dedication (if you want it):
%\vspace*{70mm}
%\begin{center}
%\renewcommand{\baselinestretch}{1.0}
%\sl
%	To \ldots
%\end{center}

\cleardoublepage

\chapter{Statement of Originality}
I declare that the work presented in the thesis is, to the best of my knowledge
and belief, original and my own work, except as acknowledged in the text, and
that the material has not been submitted, either in whole or in part, for a degree
at this or any other university.\\

Charles Murray

\cleardoublepage

\chapter{Acknowledgments}

I would like to thank my supervisor Dr. Xue Li for many constructive comments and feedback about my direction and the work I had done. I would also like to thank my family for pulling me through when I really needed it.

\cleardoublepage

\chapter{Abstract}

% Notice that all \include files are chapters -- a logical division.
% But not all chapters are \include files; some chapters are short
% enough to be in-lined in the main file.

Tree comparison systems are widely used in a number of different fields of both science and engineering. The current techniques for doing tree comparison using tree distance based metrics are limited to the operations of rename, delete and insert. This paper presents a novel approach that moves away from this paradigm to provide more information when calculating the distance than the accepted approaches. Considering that the algorithms presented are used across so many fields it is important that they provide a simple but powerful system. By using the operations rotation, switch and relabel the system is given access to not only a metric for comparing similarity but this can now be broken down further into where the similarity lies with regards to the structure, order and label difference of the nodes. 

\tableofcontents

\cleardoublepage

\listoffigures
\addcontentsline{toc}{chapter}{List of Figures}

\cleardoublepage

\listoftables
\addcontentsline{toc}{chapter}{List of Tables}

\cleardoublepage

\listofalgorithms
\addcontentsline{toc}{chapter}{List of Algorithms}

% If file los.tex begins with ``\chapter{List of Symbols}'':
% \include{los}

\cleardoublepage

\mainmatter
% By default, mainmatter has Arabic page-numbering (1,2,...).


% Chapters may be \include files, each beginning with a line like
%
%	\chapter{Title of chapter}
%
% e.g. if two chapter files were called intro.tex and theory.tex,
% we would say
%
%	\include{intro}
%	\include{theory}

\cleardoublepage

\chapter{Introduction}
Trees are among some of the most common and well-studied data structures that exist today. They have grown to the stage where there is almost no field in computer science which does not use them in some shape or form. This growth has lead to the problem of comparing different tree structures created either with different systems or generated through use of differing parameters. The problem of tree comparison is present in many fields to name but a few, biology, structured text databases\cite{Cheng.}\cite{Garofalakis.2005}\cite{Green.2004}, image analysis, automatic theorem proving and compiler optimisation\cite{Tai.1979}\cite{Zhang.1989}\cite{Kilpelainen.1995}\cite{Hoffmann.1982}\cite{Ramesh.1992}\cite{Aho.2007}\cite{Appel.2002}\cite{Grune.2000}\cite{Hutchison.2013}. An example of there use in biology is to determine the similarity between different RNA structures\cite{Zhang.1989}\cite{Jiang.1994}.

\section{Tree Comparison}
The task of tree comparison is to provide a system, with which to compare trees against each other. The current algorithms originated from string comparison and where gradually altered to work with trees\cite{Gusfield.1997}\cite{Ukkonen.1985}\cite{Wagner.1974}. This has given rise to new challenges one of which is a metric system to compare two trees against each other. The combination of the cost function and sum of operations provides a number that tells you how similar the two trees are. However it is just a number which taken out of context has little to no meaning for the system. So a classifier of some sort is often also required to compare each of the numbers to determine which of the trees is the most likely to fit the issue at hand. The problem of determining the best metric for the job has become a complex issue with more choices than ever before\cite{PhilipBille.2005}.

\section{Tree Distance Metric}
The Tree edit distance problem was first introduced by Tai\cite{Tai.1979} as a generalisation of the string edit distance problem\cite{Wagner.1974}. The goal of a tree distance metric is to determine some value that represents the similarity of the tree structures. There are a number of different metrics which can be used to determine this distance. Tree edit distance\cite{Zhang.1989}, tree alignment distance\cite{Jiang.1994} and rotation distance represent a subset of these. The most studied of these is that of tree edit distance of which tree alignment distance is a restricted case\cite{PhilipBille.2005}.

Determining a metric for a tree can be broken into two different problems. The first is finding a function for each of the operations that will define how much of an impact the operation has on the final value namely a cost function. For example in tree edit distance you have three operations relabel, insert and remove which could take on the costs of 1, 2 and 1 respectively. Although it does not have to be defined as a multiplier that function can be considerably more sophisticated. The second is determining the steps required from each of the operations to produce the final tree\cite{PhilipBille.2005} from the original, this is known as the edit script. The final tree can be one of three different types .The first is a subtree where it tries to fit one of the trees into the other. The second is a supertree which in this case a new tree is created of which both of the starting trees are subtrees of the supertree. The last is just a standard tree which both trees have some relation to.

Both the ordered and unordered versions of the problems are looked at, from an implementation and theoretical stand point. The unordered edit case it has been proven in the general case that the problem is NP-hard\cite{Arora.1998}. However under various restrictions or special cases it is possible to produce algorithms which complete in polynomial time\cite{Valiente.2003}\cite{Zhang.1996}. An example of this is if for unordered tree edit distance if a structure preserving restriction is imposed, such that disjoint subtrees are mapped to disjoint subtrees then it can be solved in polynomial time. Unordered tree alignment distance can also be solved in polynomial time for a constant degree.

For the ordered version of the problems polynomial time algorithms exists\cite{Cormen.op.2009}. These are all based on the classic technique of dynamic programming and most of them are simple combinatorial algorithms. Recently, more advanced techniques such as fast matrix multiplication have been applied to the tree edit distance problem\cite{Chen.2001} which can give the a result for the unordered case in a considerably shorter time. 

\begin{figure}
\includegraphics[scale=0.4]{Tree_of_life}
\caption{Phylogenetic tree produced by tree edit distance comparison of genomes.\cite{Letunic.01012007}}
\label{sample}
\end{figure}

\section{The Problem}
One of the fundamental problems of the current tree distance metric comparison systems is that they just provide the one number as an output it is almost impossible to distinguish from the current systems whether the difference between the trees was predominately structural or whether the order of the nodes in the tree plays a greater role. This is inherent in the system since the algorithms use delete and insert which rearrange both order and structure. 

\section{Organisation}
The rest of the document is organised as follows. Chapter 2 goes through each of the operations which form the basis of the tree distance problem and how they work. Chapter 3 goes through the algorithms themselves which are used to generated the distance and the script used to convert one tree into another. Chapter 4 goes through the proposed approach for how the experiments will be conducted and what model will be used for comparing each of the approaches. Chapter 5 defines how each of the experiments will be conducted, the variables that are used and the results obtained, comparing them against each other. Chapter 7 presents the conclusion. Chapter 7 highlights possible future work that may be conducted.

\cleardoublepage

% I will expalin the operations with diagrams and in algorithms we will do it using pseudo code.
\chapter{Operations}
All of the algorithms used for tree comparison work by generating a script of operations and then associating a cost for each of these operations. Each of the operations is explained in detail in the following sections.


\section{Relabel}
Relabel defines a function that converts the label of a node to a new one. The following figure illustrates the process.
  
\begin{figure}[htbp]
\includegraphics{start}
\includegraphics{relabel}
\caption{Illistrates the relabel of B to G.}
\label{Relabel}
\end{figure}

\section{Delete}
The delete operation is conducted by first deleting a node from the tree and then each of the children is inserted in left to right order as a subsequence. Making the children of the deleted node, the children of the parent of the deleted node. The following figure illustrates the process
  
\begin{figure}[htbp]
\includegraphics{start}
\includegraphics{delete}
\caption{Illistrates the deletion of node K.}
\label{Delete}
\end{figure}

\section{Insert}
Insert is the complement of delete. Taking a node in the tree another node is insert by making the the existing node the parent and inserting each of the children of the original node as a subsequence from left to right, so as to maintain order. The following figure illustrates the process.
  
\begin{figure}[htbp]
\includegraphics{start}
\includegraphics{insert}
\caption{Illistrates the insertion of node H.}
\label{Insert}
\end{figure}
%\subsection{Unordered Trees}
%The operations for unordered trees are similarly defined. However in this case the insert and delete operations work on subsets rather than subsequences. This is due to the fact that subsets represent unordered sets of unique symbols whereas sequences are an ordered selection of symbols. Based upon these three edit operations we define two problems which produce distance metrics for both ordered and unordered labelled trees T1 and T2.

\section{Rotation}
There are two different forms of rotation. The first is left rotation, here the node that you are rotating must be to the right of the parent. If the the node has a left child that becomes the right child of the parent of the node. The operation converts the node into the parent. Plus the parent becomes the left hand child of that node. Right rotation does the exact opposite and works with the a left node instead of a right. The operations are defined graphically below.
  
\begin{figure}[htbp]
\includegraphics[scale=0.8]{start}
\includegraphics[scale=0.8]{leftRotation}
\caption{This illustrates Left Rotation.}
\label{leftRotation}
\end{figure}
\begin{figure}[htbp]
\includegraphics[scale=0.8]{start}
\includegraphics[scale=0.8]{rightRotation}
\caption{This illustrates Right Rotation}
\label{rightRotation}
\end{figure}

\section{Switch}
Switch sees two nodes which are on the same level change positions. Such that the first  gives the second its parent and children. Also the second gives the first its parent and children. Level is defined as the depth that both nodes have from some common node in the tree.  The following illustrates the process.

\begin{figure}[htbp]
\includegraphics{start}
\includegraphics[scale=0.8]{Switch}
\caption{This illustrates switching}
\label{switch}
\end{figure}

\chapter{Algorithms}
\section{Tree Edit Distance}

The Tree Edit Distance problem was first defined by Tai, however due to the exponential time complexity of the algorithm in the worst case a number of others were developed to try and improve on this\cite{Shasha.1990}\cite{Zhang.1996} and provide algorithms which have a time complexity that is polynomial. Some examples of this are the Zhang \& Shasha and Klein algorithms which use certain rules that reduced the required running time of the algorithms while still providing the best result. 
%Both Zhang \& Shasha and Klein are popular but for different reasons. 
%Zhang \& Shasha provide an algorithm which is quicker to compute, but the Klein algorithm requires considerably less memory while trading of computing time. 
However both of these improvements although taking considerably less time to run than the Tai algorithm can still be quite slow. So the idea of constraint tree edit distance was proposed\cite{Lu.2001}\cite{Zhang.1996}\cite{Widmayer.1999}\cite{Valiente.2003}. Rather than trying to find the best possible distance in a faster time it looked at reducing the number of possible distances and tried to find a distance that would work within these constraints. The distance is determine by two things. The first is the smallest script of operations that allows one tree to be converted into another. The second is the cost function associated with each of these operations. The following gives an example of Tree edit distance in action.
   
\begin{figure}[htbp]
\includegraphics[scale=0.7]{(a)}
\includegraphics[scale=0.7]{(b)}
\includegraphics[scale=0.7]{(c)}
\caption{The first tree is the original tree which needs to be changed. The second tree is the original tree after K has been removed. The last tree is the tree after K has been inserted and C has been relabeled to E.}
\label{}
\end{figure}

\subsection{Tai Algorithm}
The Tai algorithm uses dynamic programming to produce a system which only considers four different cases. The first case is where both forests at that position in the tree are empty so zero is returned. In the second case the first forest has a node but the second one does not so a delete operation occurs. In the third case we look at two forests both with nodes. We then get the minimum of the all of the possible operations. So the system has to go through every single possibility to determine the sequence that produces the lowest distance. The operations it has to choose from are the same as the rest, delete, insert and relabel. If no node is in the same position in the second tree as the node and there is no label which is the same then a deletion occurs. In the same case for a node in the second tree an insertion occurs. In the case where both the first forest and the second forest for that node have a connection to another node in the tree due to labels but are at the wrong position a relabel takes place.
\begin{algorithm}[H]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{TaiAlgorithm}{TaiAlgorithm}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{Output}

\Input{FirstForest, SecondForest, Cost}
\Output{Distance}
\uIf{FirstForest == NULL \& SecondForest == NULL}{
	\Return Distance = 0\;
}\uElseIf{FirstForest != NULL \& SecondForest == NULL}{
	\Return \TaiAlgorithm{FirstForest-FirstNode, SecondForest} + Cost(FirstNode$\rightarrow\lambda$)\;
}\uElseIf{FirstForest == NULL \& SecondForest != NULL}{
	\Return \TaiAlgorithm{FirstForest, SecondForest-SecondNode} + Cost($\lambda\rightarrow$SecondNode)\;
}\ElseIf{FirstForst != NULL \& SecondForest != NULL}{
	\uIf{FirstNode not in SecondForest}{
		\TaiAlgorithm{FirstForest-FirstNode, SecondForest} + Cost(FirstNode$\rightarrow\lambda$)\;
	}\uElseIf{SecondNode not in FirstForest}{
		\TaiAlgorithm{FirstForest, SecondForest-SecondNode} + Cost(SecondNode$\rightarrow\lambda$)\;
	}\ElseIf{FirstNode in SecondForest \& SecondNode in FirstForest \& FirstNode != SecondNode}{
		\TaiAlgorithm{FirstNode), SecondForest(SecondNode)} - \TaiAlgorithm{FirstForest-FirstTree(FirstNode), SecondForest(SecondTree(SecondNode)} + Cost(FirstNode$\rightarrow$SecondNode)\;
	}
}
\caption{Tai Tree Edit Distance}
\end{algorithm}
%Tai algorithm looks at two forests and computes the distance based on a number of cases. The first case is where both forests are empty in this case the distance is always 0. The second case compares when the first forest is empty by the second does have some elements. In this case the distance is the sum of the number of nodes in the first forest supplied to the cost function. Case 3 is exactly the same except is looks at the first forest being empty and the second having nodes. Finally the fourth case looks at when both forests have nodes in them. In this case there are three options to consider. The first is where the position of a node in the first tree and the node with the same position in the second tree are not the same. 
\subsection{Zhang \& Shashas' Algorithm}
Zhang \& Shasha's algorithm uses the above method but with an addition to reduce time complexity. In this case the only forests that are considered are those where the root of the forest is what is define as a keyroot. The definition of a keyroot is that of either the root of a tree or any node in the tree which has a left sibling. So the forests that are created by these keyroot nodes are defined as the relevant subproblems. This then gives the Zhang \& Shasha algorithm a time complexity of $O(|T_1||T_2|min{\{D_1,L_1\}}min{\{D_2,L_2\}})$ and a space complexity of $O(|T_1||T_2|)$.\\
% Not quite sure how it deals with the subproblems to compute the distance.
\begin{algorithm}[H]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{TaiAlgorithm}{TaiAlgorithm}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{Output}

\Input{FirstTree, SecondTree, Cost}
\Output{Distance}
KeyRoots(T)
\ForEach{FirstNode}{
	\ForEach{SecondNode}{
		\TaiAlgorithm{FirstKeyForest, SecondKeyForest, Cost}
	}
}
\caption{Keyroots for Zhang and Shashas' algorithm}
\end{algorithm}
%\subsection{Kleins Algorithm}
\section{Tree Alignment Distance}
%\subsection{Tree Alignment}
Ordered tree alignment distance works by finding an optimal alignment between two trees. The algorithm then considers each of the types of nodes in the resulting alignment tree to find the distance of the two trees. The following shows an example of an alignment between two trees, depending on the cost function the distance may be 4, if only unique and opposing nodes are considered.\\
\begin{figure}[htbp]
\includegraphics[scale=0.7]{one}
\includegraphics[scale=0.7]{two}
\includegraphics[scale=0.7]{result}
\caption{Illistrates how tree alignment works.}
\end{figure}
When alignment is conduct there is three types of nodes to consider. The first is a root with two labels. For this case first go through each of the nodes in the first tree and count up all of the nodes where a label is followed by an empty label. We then go through all of the nodes in the second tree where we have an empty label followed by a label. The Second is a root with a Left label. In this case going down the right path does not need to be considered since only one tree will be present. The third is a root with a Right label. As with left only label the left path does not need to be considered since one of the trees is empty for that path.
%If you take a node. The forest of a node is all of the subtrees that would be generated if that node was the root and it was deleted.
% Determine Alginment Distance
\begin{algorithm}[H]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{AlignmentDistance}{AlignmentDistance}\SetKwFunction{ComputeForest}{ComputeForest}
\SetKwFunction{ComputeTree}{ComputeTree}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{Output}

\Input{FirstForest, SecondForest}
\Output{Distance}
Distance $\leftarrow$ 0\;
\For{p $\leftarrow$ s to $m_i$}{
	Distance $\leftarrow$ Distance + Cost\;
}
\For{q $\leftarrow$ t to $n_j$}{
	Distance $\leftarrow$ Distance + Cost\;
}
\For{p $\leftarrow$ s to $m_i$}{
	\For{q $\leftarrow$ t to $n_j$}{
		\ComputeForest{$F_1[i_s,i_p],F_2[j_t,j_q]$}
	}
}
\caption{ComputeForest: This is the main algorithm which determines the distance once a tree alignment has been found.}
\end{algorithm}

\begin{algorithm}
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{AlignmentDistance}{AlignmentDistance}\SetKwFunction{ComputeForest}{ComputeForest}
\SetKwFunction{ComputeTree}{ComputeTree}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{Output}

\Input{FirstTree, SecondTree}
\Output{Distance}
Distance $\leftarrow$ 0\;
\For{i $\leftarrow$ 1 to $T_1$}{
	Distance = Distance + \ComputeForest{$F_1[i], 0$} + Cost($l_1[i], 0$)\;
}
\For{j $\leftarrow$ 1 to $T_2$}{
	Distance = Distance + \ComputeForest{$0, F_2[j]$} + Cost($0, l_2[j]$)\;
}
\For{i $\leftarrow$ 1 to $T_1$}{
	\For{j $\leftarrow$ 1 to $T_2$}{
		\For{s $\leftarrow$ 1 to $m_i$}{
			\ComputeForest{$F_1[i_s, i_{mi}], F_2[j]$}\;
		}
		\For{t $\leftarrow$ 1 to $n_j$}{
			\ComputeForest{$F_1[i], F_2[j_t, i_{nj}$}\;
		}
		\ComputeTree{$D(T_1[i], T_2[j])$}\;
	}
}
\caption{ComputeTree}
\end{algorithm}
%\subsection{Jiang, Wang, Zhang algorithm}

\section{Tree Rotation Distance}
This section goes through the classical rotation distance and how it has been converted to work in a system that provides unordered trees.
\subsection{Rotation Distance}
Rotation distance is not a new concept, when trees were first considered and people were trying to find algorithms which would balance those trees. Rotation distance was considered to try and determine how efficient those algorithms were. The reason it did not see large amounts of wide spread use where others have taken up the mantle is due to the fact that no algorithm had been found that allowed rotation distance to be calculated in polynomial time, which given the time complexity of even these algorithms would have proposed a problem. The other reason is that the use of these algorithms tends to be either against large streams of data where time is a luxury or against very large pieces of data done in a batch fashion which already take quite a considerable amount of time so people want it to be shorter not longer.

\subsection{Tree Rotation Distance}
To describe the algorithm the following structure will be used for each of the nodes.\\
%Structure of Node.
\begin{algorithm}[H]
\SetAlgoLined
Parent $\leftarrow$ Parent of the node\;
Child1 $\leftarrow$ Left child of the node\;
Child2 $\leftarrow$ Right child of the node\;
Label $\leftarrow$ Label of Node\;
\caption{Attributes of a Node}
\end{algorithm}

The following algorithm represents the skeleton of the Tree Rotation Distance algorithm. Like all of the others it is recursion based, however unlike the others it provides not only the distance but also the other metrics that were used so that the program can gain a better in-site into  whether the difference was in the labels, order or structure of the nodes. The other thing worth mentioning is that the operations are determined in the order of Switch, Rotation and Relabel. This is important otherwise the algorithm will provide a distance which is not optimal as has been defined. This comes down to the restriction of only switching nodes at the same level. This creates the case that switches must be taken when the opportunity arises and so are of higher precedence than the other operations. Also relabels must always come last because they are only there for a very specific case and should not be used for anything other than that case.\\
% Determine Distance
\begin{algorithm}[H]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{DetermineSwitches}{DetermineSwitches}
\SetKwFunction{DetermineRotations}{DetermineRotations}
\SetKwFunction{DetermineRelabel}{DetermineRelabel}
\SetKwFunction{DetermineDistance}{DetermineDistance}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{FirstRoot, SecondRoot, Cost}
\Output{Distance, Switches, Relabel, Rotations}
Switches $\leftarrow$ \DetermineSwitches{FirstRoot, SecondRoot} $\times$ Cost.Switch\;
Rotations $\leftarrow$ \DetermineRotations{FirstRoot, SecondRoot} $\times$ Cost.Rotation\;
Relabels $\leftarrow$ \DetermineRelabel{FirstTree, SecondTree} $\times$ Cost.Relabel\;

Distance $\leftarrow$ Switches + Rotations + Relabels\;
MetricsStart $\leftarrow$ \DetermineDistance{FirstRoot.Child1, SecondRoot.Child1, Cost}\;
MetricsEnd $\leftarrow$ \DetermineDistance{FirstRoot.Child2, SecondRoot.Child2, Cost}\;
Distance $\leftarrow$ Distance + MetricsFirst[0] + MetricsEnd[0]\;
Switches $\leftarrow$ Switches + MetricsFirst[1] + MetricsEnd[1]\;
Rotations $\leftarrow$ Rotations + MetricsFirst[2] + MetricsEnd[2]\;
Relabels $\leftarrow$ Relabels + MetricsFirst[3] + MetricsEnd[3]\;
\Return{Distance, Switches, Rotations, Relabels}\;

\caption{Determines the distance between the two Trees.}
\end{algorithm}

To describe the algorithm each of the operations will be split into there own section and the operation along with the cases which have to be considered will be gone through in pseudo code. The first of which will be the switch function.The following is an example of the basic switch operation. It is designed to ensure that the switch can only happen on the one level.\\
% Switch a node.
\begin{algorithm}[H]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{NodeDepth}{NodeDepth}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{NodeStart, NodeFinish}
\Output{Switch Node}
\SetAlgoLined
\If{\NodeDepth{NodeStart} == \NodeDepth{NodeEnd}} {
	NodeStartParent $\leftarrow$ NodeStart.Parent\;
	NodeStartChild1 $\leftarrow$ NodeStart.Child1\;
	NodeStartChild2 $\leftarrow$ NodeStart.Child2\;
	NodeEndParent $\leftarrow$ NodeEnd.Parent\;
	NodeEndChild1 $\leftarrow$ NodeEnd.Child1\;
	NodeEndChild2 $\leftarrow$ NodeEnd.Child2\;
	NodeStart.Parent $\leftarrow$ NodeEndParent\;
	NodeStart.Child1 $\leftarrow$ NodeEndChild1\;
	NodeStart.Child2 $\leftarrow$ NodeEndChild2\;
	NodeEnd.Parent $\leftarrow$ NodeStartParent\;
	NodeEnd.Child1 $\leftarrow$ NodeStartChild1\;
	NodeEnd.Child2 $\leftarrow$ NodeStartChild2\;
}
\caption{Tree Switch}
\end{algorithm}

The following provides a system for determining the depth of a Node based on the Root that has been defined for that node. This is very useful for the switch operation as we can check that the nodes are on the same level.\\
% Get depth of node.
\begin{algorithm}[H]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{Node, Root}
\Output{NodeDepth}
\SetAlgoLined
NodeDepth $\leftarrow$ 0\;
\While{Node.Parent != Root}{
	NodeDepth $\leftarrow$ NodeDepth + 1\;
}
\caption{Determine depth of node}
\end{algorithm}

The switch operation by itself does not define the distance for the switches. This is a process which requires a number of different steps. The first is to determine which nodes in both trees need to be switched. Which is outlined in the below algorithm. Determining the required switches for this stage of the process is done on a labelling basis looking for nodes which are descents of the first child but in the second tree and descents of the second child and vice versa.
% Need to consider the root and number of nodes which should be located on each side.
% Find all of the possible switches that need to be made.
\begin{algorithm}[h]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{SplitTree}{SplitTree}\SetKwFunction{Union}{Union}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
%Iterate through all nodes in both trees.
%If in one tree switch 
%Look through all of the pairs which are less than root are there any that need to be
%change in ours.
%we get a list of nodes and split it by the root label and then see if we have anything 
%from an union of first from the second and second from the first.
\Input{FirstTree, SecondTree}
\Output{StartSwitches, EndSwitches}
(FirstStart, FirstEnd) = \SplitTree{FirstTree}\;
(SecondStart, SecondEnd) = \SplitTree{SecondTree}\;
StartSwitches = \Union{FirstStart, SecondEnd}\;
EndSwitches = \Union{FirstEnd, SecondStart}\;
\caption{Determine if switch required}
\end{algorithm}

Once it has been determined that a switch needs to occur, there are several cases to consider for each of the nodes being switched. The first is doing a switch between two labelled nodes which are already on the same level. In this case all that need be done is do the switch operation and remove the two nodes for the switch lists produced by the two trees. The following pseudo code shows how this works.
% Switching Between 2 labeled nodes. Need to consider if we have some avaiable that are not on the same level.
\begin{algorithm}[h]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{SplitTree}{SplitTree}\SetKwFunction{Union}{Union}
\SetKwFunction{length}{length}\SetKwFunction{Switch}{Switch}
\SetKwFunction{Remove}{Remove}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
%Iterate through all nodes in both trees.
%If in one tree switch 
%Look through all of the pairs which are less than root are there any that need to be
%change in ours.
%we get a list of nodes and split it by the root label and then see if we have anything 
%from an union of first from the second and second from the first.
\Input{StartSwitches, EndSwitches, StartTreeSwitches, EndTreeSwitches}
\Output{RemainingSwitches}
\eIf{\length{StartSwitches} <= \length{EndSwitches}}{
	\For{node $\leftarrow 0$ \KwTo \length{StartSwitches}}{
		\Switch{StartSwitches[0], EndSwitches[0]}\;
		\Remove{StartSwitches, StartSwitches[0]}\;
		\Remove{EndSwitches, EndSwitches[0]}\;
	}
}{
	\For{node $\leftarrow 0$ \KwTo \length{EndSwitches}}{
		\Switch{EndSwitches[0], StartSwitches[0]}\;
		\Remove{StartSwitches, StartSwitches[0]}\;
		\Remove{EndSwitches, EndSwitches[0]}\;
	}
}
\caption{Switch on you have two nodes at the same level which need to be switched.}
\end{algorithm}

Once all of the switches between labels on the same level have been exhausted, the next case to consider is that of switches between a labelled node and a non-labeled node. This is more complicated since the children must also be considered for each of the labelled nodes. This is akin to doing a delete and then an insert operation. The following goes through how this system works.
% Switching between an empty node and a labelled node.
\begin{algorithm}[h]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{EmptyNodes}{EmptyNodes}\SetKwFunction{NodeDepth}{NodeDepth}
\SetKwFunction{Append}{Append}\SetKwFunction{Switch}{Switch}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{Switches, Tree}
\Output{RemainingSwitches}
\ForEach{SwitchNode in Switches}{
	Depth = \NodeDepth{SwitchNode, Tree.Root}\;
	\ForEach{Empty in \EmptyNodes{Tree.Root}}{
		\If{Depth, \NodeDepth{Empty, Tree.Root}}{
			\Switch{Empty, SwitchNode}\;
			%\Append{CorrectDepth, Empty}\;
		}
	}
}
\caption{Switch in the case of Empty on same level.}
\end{algorithm}

The final case is that where a switch has to happen but there is no slots on the current level that can be used to conduct the switch with. In this case a switch must be accompanied by a rotation to change the levels of the nodes. It is important that only rotation be used for this since the tree will be split into forests as the recursive algorithm parses it. The following shows in pseudo code how this is accomplished.
\begin{algorithm}[h]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{EmptyNodes}{EmptyNodes}\SetKwFunction{NodeDepth}{NodeDepth}
\SetKwFunction{Append}{Append}\SetKwFunction{Switch}{Switch}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{Switches, Tree}
\Output{Rotations, Switches}


\caption{Provides switches to other levels in the tree.}
\end{algorithm}

The second operation is that of rotation. This is just a psuedocode representation of a binary rotation. Non Binary Rotations are possible but far hard to implement and maintain. So for the sake of simplicity binary rotations are used.\\
% Rotate node.
\begin{algorithm}[H]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{Node}
\Output{Rotated Node}
\SetAlgoLined
NodeParent $\leftarrow$ Node.Parent\;
NodeChild1 $\leftarrow$ Node.Child1\;
NodeChild2 $\leftarrow$ Node.Child2\;
\eIf{Node.Parent.Child1 == Node}{
	Node.Parent $\leftarrow$ NodeParent.Parent\;
	NodeParnet.Child2 $\leftarrow$ NodeChild1\;
	Node.Child1 $\leftarrow$ NodeParent\;
}{
	Node.Parent $\leftarrow$ NodeParent.Parent\;
	NodeParnet.Child1 $\leftarrow$ NodeChild2\;
	Node.Child2 $\leftarrow$ NodeParent\;
}
\caption{Tree Rotation}
\end{algorithm}

The operation rotation does not represent the algorithm by itself. It is also required to determine when best to do a rotation and that is defined in the following function. Since rotations only happen for the root of each subtree only four cases need be considered. The first is that were the root of the second tree exists as some node other than root in the first tree. In this case the node in the first tree is brought up to the root position of the subtree. The second case is just the complementary of the first case. The third case is where neither root is present in each of the trees. In this case two nodes are located which are unique to each of the trees and rotated to the root node and relabelled. The final case is where both nodes are the same label. In this case nothing need be done.\\
% Determine Rotation Distance
\begin{algorithm}[H]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{Append}{Append}\SetKwFunction{Rotation}{Rotation}
\SetKwFunction{FindUniqueNodes}{FindUniqueNodes}
\SetKwFunction{GetNodeWithLowestDepth}{GetNodeWithLowestDepth}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{FirstRoot, SecondRoot}
\Output{Rotation Distance}
%SecondRoot exists in First tree.
\ForEach{node in FirstRoot}{
	\If{node.Label == SecondRoot.Label}{
		\While{node.Child1 != FirstRoot $\lor$ node.Child2 != FirstRoot}{
			\Rotation{node}\;		
		}
		\Return{}\;
	}
}
%FirstRoot exists in Second tree.
\ForEach{node in SecondRoot}{
	\If{node.Label == FirstRoot.Label}{
		\While{node.Child1 != SecondRoot $\lor$ node.Child2 != SecondRoot}{
			\Rotation{node}\;		
		}
		\Return\;
	}
}
\caption{Determine Rotation Distance}
\end{algorithm}

The final operation used by the system is that of relabeling. As it was with the other operations it code to do the function is quite basic however the code to determine when and where this should run is considerably more complicated.
% Relabel a node.
\begin{algorithm}[h]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{Node, Label}
\Output{Relabel Node}
Node.Label = Label
\caption{Relabel Node}
\end{algorithm}

There is only one case where a relabel operation is required and this is when we need a node in a certain location with a certain label. This brings about two different occurances. The first is that there is already a label there which we just need to rename since it is not being used elsewhere. The second is we have a missing node and that we need to move up an unused node into this location and relabel it. The definition of an unused node is one where its label does not represent a label in another tree and it is in a position which is not occupied in the other tree. In the case where a node cannot be found a NULL node can be provided to fill the gap, although this practice is frowned upon.

The following provides a pseudocode example for how the insert operation works.
% Need to go through an figure out exactly how the system decides the order that is done when a insert occurs.
% Insert a node.
\begin{algorithm}[h]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{Parent, Node, Child}
\Output{Inserted Node}
Node.Parent = Parent
\eIf{Child == 1} {
	Node.Child1 = Parent.Child1\;
	Parent.Child1 = Node\;
}{
	Node.Child2 = Parent.Child2\;
	Parent.Child2 = Node\;
}
\caption{Insert Node}
\end{algorithm}


The following defines a delete operation for the tree edit distance and tree alignment distance metrics.
% Need to determine the order that the nodes are processed during a deletion.
% Delete a node.
\begin{algorithm}[h]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{Node}
\Output{Deleted Node}
NodeChild1 $\leftarrow$ Node.Child1\;
NodeChild2 $\leftarrow$ Node.Child2\;
Node.Parent.Child1 $\leftarrow$ Node.Child1\;
Node $\leftarrow$ Node.Child1\;

\While{Node != NULL} {
	Node.
}
\caption{Delete Node}
\end{algorithm}

% Find all Empty nodes in a tree.
\begin{algorithm}[h]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{Append}{Append}\SetKwFunction{NodeDepth}{NodeDepth}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{Node}
\Output{EmptyNodes}
\ForEach{Empty in Node}{
	\If{Empty == NULL}{
		\Append{EmptyNodes, (node, \NodeDepth{Empty, Node})}
	}
}
\caption{Identify Empty Nodes}
\end{algorithm}


% Split the tree into two subtrees based on the children.
\begin{algorithm}[h]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{Append}{Append}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{Node}
\Output{Start, End}
\ForEach{StartNode in Node.Child1}{
	\Append{Start, StartNode}\;
}
\ForEach{EndNode in Node.Child2}{
	\Append{End, EndNode}\;
}
\caption{Split: Determine nodes in the front and back of a tree from a node.}
\end{algorithm}

% Find All the pairs of nodes with the same label.
\begin{algorithm}[h]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{Append}{Append}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{FirstTree, SecondTree}
\Output{Pairs}
\ForEach{FirstNode in FirstTree}{
	\ForEach{SecondNode in SecondTree}{
		\If{FirstNode.Label == SecondNode.Label}{
			\Append{Pairs, (FirstNode, SecondNode)}\;
		}
	}
}
\caption{Determine tree node pairs}
\end{algorithm}

% Determine Distance Wrapper
\begin{algorithm}[H]
\SetKwFunction{DetermineDistance}{DetermineDistance}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{FirstTree, SecondTree, Cost}
\Output{Distance, Switches, Relabel, Rotations}
\Return \DetermineDistance{FirstTree.Root, SecondTree.Root, Cost}\;
\caption{Wrapper for determining distance.}
\end{algorithm}

%Find node from list with lowest depth.
\begin{algorithm}[H]
\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
\SetKwFunction{Append}{Append}\SetKwFunction{Rotation}{Rotation}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

\Input{FirstRoot, SecondRoot, Unique}
\Output{Depth Node}
current\;
depth $\leftarrow$ 0\;
\ForEach{node in Unique[0]}{
	\If{node.Depth < Depth}{
		current $\leftarrow$ node.Node\;
	}
}
\ForEach{node in Unique[1]}{
	\If{node.Depth < depth}{
		current $\leftarrow$ node.Node\;
	}
}
\Return{current}\;
\caption{Depth: Find the node with the lowest depth.}
\end{algorithm}

\cleardoublepage

\chapter{Proposed Approach}
The proposed approach is to look at using tree rotation distance as a metric and to compare it against the widely used and studied tree edit distance namely Klein, Zhang \& Shasha and Jiangs' tree alignment distance algorithm. The experiments will be broken up into three different categories based on the trees. The first will be to do a comparison of all the algorithms when all that is provided is an ordered binary tree each with the same sets of labels, this will also test the subtree functionality of the algorithms by providing trees of different sizes. This is important since outside of the general case of finding a comparison between trees it is also important to find subtrees\cite{Gupta.1998}\cite{Augsten.}\cite{Alabbas.2012}. The following sections describe the propose approach in detail.

\section{Model}
Since the tree edit distance, tree alignment distance and tree rotation distance provide quite different metrics it is necessary to define an overarching model which allows them to be compared in the same space. Considering that each of the metrics produces a real number distance as an output we define the model as a classifier which has a range of thresholds from 0 to 5 times the size of the greatest tree. Here the size is the number of nodes in the tree. Each of the metrics is then given a number of different trees to consider and the output produced by each. This was done using the best practice from the following papers\cite{Cleary.2002}\cite{Zerling.1985}.

To reduce the complexity of the problem there will be two types of trees the first ones are modifications from the original tree. The second type is randomly generated trees which should have little to no similarity to the tree that is being compared against. The goal is to determine the threshold\cite{Gavrila.}\cite{YanhongZhai.2006} which provides the lowest amount of error for each of the algorithms. In this model a tree will be considered part of the system if it has only been changed by at most 70\%. This value can be obtained with any combination of the following operations; rotate, insert, delete, switch and relabel. 
% Might want to consider defining a formula here.
The 70\% is determined by the number of nodes changed divided by the total number of nodes. Since doing certain operations will advantage some and put others at a disadvantage each of the operations will be randomly allocated and limited to a certain number in total. 

In doing this the model is acting as a classifier to try and determine trees which are examples of the original tree. In terms of XML trees a number of others have considered similar methods\cite{Bouchachia.}\cite{Wang.2012}. This approach differs in that firstly JSON is used not XML which presents its own challenges and a new algorithm is being considered namely Tree Rotation Distance. Due to how the model works it also gives great scope to look at change detection\cite{Chawathe.1997}\cite{Chawathe.1996} in the tree.

\section{Algorithm}
Looking at the problem of developing a distance metric it can be seen that the problem has a number of subsets. Firstly a sequence of operations must be determine to convert the first tree into the second.
Going deeper into this in order to determine the sequence you need to decide on where the algorithm will start in the tree and what the rules would be to determine both when it would end and what operation would be done at each stage. 
Secondly a cost function must be defined for each of the operations. 

As with tree edit distance and tree alignment distance it is preferable if the rules could be split up based on the operations that were defined and would not require backtracking through the operations to take a different route for a decision. So to accomplish this each primitive should only affect the tree and not each other. 

This problem has a further 3 subsets. The first is computing the distance for an ordered tree with a defined set of labels which occur in both trees. This does not really represent a real world example but does provide a decent starting block with which to develop the algorithm, since it limits the algorithm to only requiring one operation namely rotation. Since the tree is ordered and both trees use a defined set of labels neither relabel or switch are required. 
%(I want to say more here just not sure what, need to make the rotation distance algorithm seem bigger than what I am currently defining it.)

Secondly you need to consider an operation where the labels are from different sets but they are still ordered. Since if the labels were from completely different sets the tree would be unordered so to maintain order the sets are only sudo different meaning that they do each have different elements but a majority of the elements in the set are the same. This provides an ideal stage to define the relabel function and under what circumstances it would be best used. 

The third and final stage is that of a completely unordered tree. This is where the switch operation comes in to its own. Since its primary and only usage is to reorder the tree by allowing the switch between two elements.

By separating the system out into rotation, switch and relabel it can also provide us with some new metrics which the other systems do not provide. The tree edit distance and the tree alignment distance provided useful metrics to comparing two trees in their entirety. However this new system gives greater control by allowing the comparator to compare on three different planes namely, the similarity of the two structures, the closeness of the of the order of the elements and the similarity of the labels used by both structures. 

Therefore the decision was made to use the operations rotation, switch and relabel, and define them only for certain jobs that would be required to convert one tree into another. 
Considering that in some systems the trees that are being compared could be quite large or it is not possible due to other constraints to see the entire tree at once. Such as in a data streaming model it is preferable if the algorithm did not require access to the entire tree at once. 

\section{Rotation Distance}
The first problem of developing an algorithm for to provide tree distance metrics using rotations is to determine an algorithm which would be able to efficiently for ordered trees determine the rotation distance required to convert one tree into another in a reasonable time. 
There are other algorithms in existence\cite{Cleary.2002}\cite{Dehornoy.2010} however they did not prove useful as they took the problem into another space and this would have lead to issues when I added the switch and relabel operations to deal with unordered trees. So I decided not to use them and find another algorithm that would do the job. 

\section{Error}
Error is used to help determine how the algorithms work when in the classifier. This is vital to pattern matching\cite{Amir.2001}\cite{Dubiner.1994}\cite{Hoffmann.1982}\cite{Ramesh.1992}\cite{Wu.2010}\cite{Ukkonen.1985} as the distance metrics provide just that a metric. This will only give a sense of what could be the correct threshold not what is. To accomplish this we use both MAE and MSE which provide a way to look at the error from two different points of view.
\subsection{Mean Absolute Error}
The Mean absolute error (MAE) is a measure of the average difference between the predicted results and the expected results. The equation is given below where N is the number of predictions, q is the true value and p is the predictions that were provided by the system.
\[MAE=\frac{\sum_{i=1}^{N}|p_i-q_i|}{N}\]
\subsection{Mean Square Error}
Mean square error is very similar to MAE however it squares the differences in error so that the final result is far more spread out especially for large values. This makes it useful in the case of this problem since it is better at spreading out the results which makes it easier to identify the best algorithm.
\[MSE=\frac{{\sum_{i=1}^{N}{|p_i-q_i|}^{2}}}{N}\]

\cleardoublepage

\chapter{Experiments and Results}
A number of experiments were conducted to determine the prediction ability of tree rotation distance when compared to tree alignment distance and tree edit distance. It was important in to determine the different situations in which in each of the systems worked well so four experiments were conducted to determine how each of the systems worked in an ordered, subtree and unordered environment. 
\section{Experiment 1 Determine Best Cost Function}
The first problem in determining whether a distance metric is going to be useful for a situation is to determine the best cost function for a given sample of trees. Each of the algorithms have different definitions of what constitutes a operation with regards to cost. So for each of the examples a function that provides the lowest amount of error is required. To determine this, firstly a selection of comparisons were chosen in which the structure of the two trees varied considerably. Secondly a number of cases where considered as a cost function for each of these comparisons. These cases are highlighted in the tables below.

\begin{table}[h]
\caption{\sl Cost Function Cases Tree Edit Distance}
\label{costEdit}
\begin{center}
\begin{tabular}{ | l | l | l | l | l | }
\hline
Cases & Relabel & Insert & Delete & Result(MSE)\\ \hline
1 & 0 & 0 & 1 & 0.2468\\ \hline
2 & 0 & 1 & 0 & 0.2378\\ \hline
3 & 0 & 1 & 1 & 0.2015\\ \hline
4 & 1 & 0 & 0 & 0.2894\\ \hline
5 & 1 & 0 & 1 & 0.2387\\ \hline
6 & 1 & 1 & 0 & 0.2349\\ \hline
7 & 1 & 1 & 1 & 0.1905\\ \hline
\end{tabular}
\end{center}
\end{table}

After going through the results of the tree edit distance cases it was determined that the case where all relabel, delete and insert were given a cost function of 1 produced the best results. Just giving relabel a cost produced a system that would favor similar named nodes and wouldn't care if the structure was completely different. Having just insert and/or delete create a system which would only care about the structure and not consider the labels. Finally with a relabel and either an insert or a delete operation it seemed that it would only take into account certain areas of the tree structure and for certain edge cases would give rather different results.

\begin{table}[h]
\caption{\sl Cost Function Cases Tree Alignment Distance}
\label{costAlign}
\begin{center}
\begin{tabular}{ | l | l | l | l | }
\hline
Cases & Opposing & Unique & Result (MSE) \\ \hline
1 & 0 & 1 & 0.2750\\ \hline
2 & 1 & 0 & 0.2938\\ \hline
3 & 1 & 1 &  0.1563\\ \hline
\end{tabular}
\end{center}
\end{table}

The alignment distance did have a number of surprises in the results. Although both unique and opposing came out very similar unique had a far greater spread of values where as opposing was far more consistant in what was produced. However both of them combined proved to be the best approach as can be seen.

\begin{table}[h]
\caption{\sl Cost Function Cases Tree Rotation Distance}
\label{costRot}
\begin{center}
\begin{tabular}{ | l | | l | l | l | l | }
\hline
Cases & Rotate & Switch & Relabel & Results(MSE)\\ \hline
1 & 0 & 0 & 1 & 0.2846\\ \hline
2 & 0 & 1 & 0 & 0.2451\\ \hline
3 & 0 & 1 & 1 & 0.2234\\ \hline
4 & 1 & 0 & 0 & 0.3562\\ \hline
5 & 1 & 0 & 1 & 0.2476\\ \hline
6 & 1 & 1 & 0 & 0.2785\\ \hline
7 & 1 & 1 & 1 & 0.2167\\ \hline
\end{tabular}
\end{center}
\end{table}

Rotate showed that it was very capable of comparing the structure of the tree however, since it does not take into account labels this brought it down. In ordered trees switching proved basically useless since it is designed for unordered trees. Relabel showed how similar the labels were and to a certain degree gave a metric for structural similarity although this was hard to define explicitly. As far as the combination options go Rotate and Relabel provided the best system for ordered trees, probably since switch is only required for unordered trees. However the final winner was that of using all of the distances together. This provided the best result in the general case.

\section{Experiment 2 Randomly Generated Ordered Trees}
In the first experiment the goal is to determine how each of the distance metrics performed in an ordered environment. In this experiment a total of 100 trees were randomly generated and then randomly altered to produce a total of 2000. Then another 4000 trees were randomly generated. Each of the trees had a limit of 100 nodes some were of cause higher and lower than that. Since order is important in this experiment the only operations allowed were relabel, rotation, insert and delete. However insert is not allowed to introduce the same variable twice. As with the proposal the system was limited to a threshold between 0 and 5 times the total number of nodes for the experiment so the limit was set at 500 operations. Each of the first randomly generated trees was then provide to the algorithms to compare against. The 20 trees generated by altering the structure were then provided to get a distance from the algorithm. Another 20 trees were also selected from the 4000 that were generated and provided to the algorithms to determine the distance for them. Each of the randomly generated trees was considered a negative and the 20 trees which were generated by random functions were considered positives. The best threshold was then found by reviewing each of the possible thresholds and determining which provided the lowest error for that particular tree. This was done for each of the algorithms. We then looked at each of the errors for each of the algorithms and the winner was determined by which one provided the least amount of error overall.
\begin{table}[h]
\caption{\sl Results for Randomly Generated Ordered Trees}
\label{unorderedResults}
\begin{center}
\begin{tabular}{ | l | l | l |}
\hline
Tree Edit Distance & Tree Alignment Distance & Tree Rotation Distance \\ \hline
0.2 & 0.2 & 0.2 \\ \hline
0.25 & 025 & 0.4 \\ \hline
0.05 & 0.15 & 0.1 \\ \hline
0.5 & 0.5 & 0.5 \\ \hline
\end{tabular}
\end{center}
\end{table}

\section{Experiment 3 Randomly Generated Unorder Trees}
In the second experiment the goal is to compare each of the systems to determine how they did in a situation where everything was possible. As with the previous experiment this experiment used 100 randomly generated trees. It also then randomly generates another 2000 trees by using a random assortment of the operations. We also generate the other random 4000 trees just as in the previous experiment. The main difference between this experiment and the previous however this time rather than just make changes based on operations each tree was then compared with each other tree to determine the distance based on the different algorithms.  Each of these trees was then passed through an algorithm to determine their distance when compared with the original tree that the system was generated from. As before a threshold range was set between 0 and 500 operations the best threshold value was then chosen from this range.

\begin{table}[h]
\caption{\sl Results for Randomly Generated Unordered Trees}
\label{unorderedResults}
\begin{center}
\begin{tabular}{ | l | l | l |}
\hline
Tree Edit Distance & Tree Alignment Distance & Tree Rotation Distance \\ \hline
0.25 & 0.05 & 0.15 \\ \hline
0.25 & 0 & 0.15 \\ \hline
0.05 & 0.25 & 0.25 \\ \hline
0.15 & 035 & 0.2 \\ \hline
\end{tabular}
\end{center}
\end{table}
%\section{Experiment 4 Real World Trees}
%To conduct the experiment on real world examples of trees, JSON files from jira were obtained and used to test out the algorithms. For an example of these trees look in the appendix. To prevent any favoritism in the labels the data was obtain from two different projects. The job of the distance metrics was to determine the likelihood of each of the JSON trees being from one of the projects. One of the trees was selected at random to act as the original training sample from each of the trees. To fully test out each of the systems two subsets of the trees where considered, namely those with a changelog and those without. As with the previous experiments the best possible threshold was found for each of the data sets and used to create the results. The following shows the results obtained from doing this.
%\begin{table}[h]
%\caption{\sl Results for Real World Trees}
%\label{unorderedResults}
%\begin{center}
%\begin{tabular}{ | l | l | l | l |}
%\hline
%Case & Tree Edit Distance & Tree Alignment Distance & Tree Rotation Distance \\ \hline
%First Project & 0.15 & 0.2 & 0.2 \\ \hline
%First Project Changelog & 0.3 & 0.35 & 0.1 \\ \hline
%Second Project & 0.05 & 0.2 & 0.1 \\ \hline
%Second Project Changelog & 0.2 & 0.25 & 0.15 \\ \hline
%\end{tabular}
%\end{center}
%\end{table}



\cleardoublepage

\chapter{Conclusions}
This paper introduced a new approach to dealing with problem of tree distance metrics for document cluster systems. By using rotations and switches in place of insertions and deletions it is possible to deal with a greater array of different document changes and get useful metrics than was previous possible. By looking at a number of cases for the cost function it was possible to show in what situation having different kinds of cost functions would be worthwhile if you have an idea of what the data will look like before it is received. 

The results of the experiments show that although Tree Rotation Distance can be a very useful metric in certain situations, it is still not quite as good as the current best practice of Tree Edit Distance. Producing higher error in the general case with respect to Mean Absolute Error and Mean Squared Error. At least in a simple use case of its predictive power. However given that the time complexity of $O(|T_1| + |T_2|^{2}|D_1|^{2})$ and a space complexity of $O(|T_1| + |T_2|)$. This allows the system to run under considerably less memory requirements. Also given how the algorithm works it will also run in $O(|T_1| + |T_2|^2log(T_1)^2)$ if the tree is balanced which is considerably faster than any of the other popular algorithms so it could be used to find a slightly less accurate answer in considerably less time.

\chapter{Future Work}
Considering how devoid the Tree Rotation Distance is from the Tree Edit Distance metric it would be worthwhile in future work if a hybrid system between the two was considered. A very small amount of work was conduct during the course of this thesis to see if it would be a reliable system however since it was beyond the scope of this thesis, the question was not pursued with the same rigour.

Inclusion\cite{Alonso.1993}\cite{Kilpelainen.1995}\cite{Valiente.2003} is also a well studied problem and it would be worth looking at how this system compares with the current tree edit distance system especially across large number of trees which each need to be compared equally.

It would be worthwhile looking further into how different and more complex systems for the cost functions may be able to provide better results in certain circumstances than that of just using the system of having all of the operations given a cost of one which tends to be the general theme of the research that has currently been conducted to date on this problem. This could also be useful for considering hybrids of these systems to produce better results.

Considering the large amount of work conducted with regards to XML streams it may be worthwhile looking into how the system would compare with XML instead of JSON, although this is probably not worthwhile since the system is fairly abstract. 

Due to the nature of the Tree Rotation Distance it may be better used in certain situtations than in others when compared with Tree Edit Distance or Tree Alignment Distance so it would be worthwhile going through different system in which these metrics are used and compare it against them.



\addcontentsline{toc}{chapter}{Bibliography}
\bibliographystyle{plain}
\bibliography{Thesis}

\appendix

% Chapters after the \appendix command are lettered, not numbered.
% Setting apart the appendices in the table of contents is awkward:

\newpage
\addcontentsline{toc}{part}{Appendices}
\mbox{}
\newpage

% The \mbox{} command between two \newpage commands gives a blank page.
% In the contents, the ``Appendices'' heading is shown as being on this
% blank page, which is the page before the first appendix.  This stops the
% first appendix from be listed ABOVE the word ``Appendices'' in the
% table of contents.

% \include appendix chapters here.

%\chapter{JSON Trees}
%\section{Project Tree}
%\lstinputlisting[language=javascript, firstnumber=1]{project.json}

%\section{Project Changelog Tree}
%\lstinputlisting[language=javascript, firstnumber=1]{changelog.json}

\chapter{Program listings}

\section{Node}
\lstinputlisting[language=Python]{../node.py}

\section{Tree}
\lstinputlisting[language=Python]{../tree.py}

\section{TED Tree}
\lstinputlisting[language=Python]{../tedtree.py}

\section{Model}
\lstinputlisting[language=Python]{../model.py}

\section{Generate Tree}
\lstinputlisting[language=Python]{../generatetree.py}

\section{Rotation Distance Ordered}
\lstinputlisting[language=Python]{../rotdistordered.py}

\section{Rotation Distance Unordered}
\lstinputlisting[language=Python]{../rotdistunordered.py}

\section{JSON Parser}
\lstinputlisting[language=Python]{../JsonParse.py}

\section{Program}
\lstinputlisting[language=Python]{../program.py}

\section{Classifier}
\lstinputlisting[language=Python]{../classifier.py}

\section{Display Tree}
\lstinputlisting[language=Python]{../displaytree.py}

\section{Run Process}
\lstinputlisting[language=Python]{../runprocess.py}

\cleardoublepage

\end{document}
